/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
/*
//
 //取原链表中的节点，然后头插到newhead新链表中
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;

    //循环遍历取出链表节点
    while (cur) {
        //先拿到cur->next
        struct ListNode* next = cur->next;
        //进行头插
        cur->next = newhead;
        //newhead指向新的头结点
        newhead = cur;
        //接着遍历原链表的下一个节点
        cur = next;
    }

    return newhead;
}
*/


struct ListNode* reverseList(struct ListNode* head) {
    //如果传入的链表头指针head为空，直接返回NULL，因为空链表不需要反转
    if (head == NULL) {
        return NULL;
    }

    struct ListNode* n1, * n2, * n3;
    n1 = NULL;
    n2 = head;
    n3 = head->next;

    while (n2) {
        //翻转
        n2->next = n1;
        //迭代往后走
        n1 = n2;
        n2 = n3;
        if (n3) {
            n3 = n3->next;
        }
    }
    return n1;
}